package cn.jdemo.algorithm.hard;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * trap(i) = min(lmax,rmax) - height(i);
 *
 * 暴力 + 备忘录
 */
public class Trap {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int trap = new Trap().trap(height);
        System.out.println(trap);
    }

    /** 备忘录  */
    private Integer[] lmaxs;
    private Integer[] rmaxs;

    public int trap(int[] height) {
        lmaxs = new Integer[height.length];
        rmaxs = new Integer[height.length];
        int res = 0;
        int length = height.length;
        for (int i = 0; i < length; i++) {
            int tmp = Math.min(lmax(height, i), rmax(height, i)) - height[i];
            // res = Math.max(res, tmp);
            res += tmp;

        }
        return res;
    }

    public int lmax(int[] height, int cuur){
        if (cuur < 0){
            return 0;
        }
        if (lmaxs[cuur]!=null){
            return Math.max( lmaxs[cuur] , height[cuur] );
        }
        int lmax = lmax(height, cuur - 1);
        lmaxs[cuur] = lmax;
        return Math.max( lmax , height[cuur] );
    }

    public int rmax(int[] height, int cuur){
        if (cuur >= height.length){
            return 0;
        }
        if (rmaxs[cuur]!=null){
            return Math.max( rmaxs[cuur] , height[cuur] );
        }
        int rmax = rmax(height, cuur + 1);
        rmaxs[cuur] = rmax;
        return Math.max( rmax , height[cuur] );
    }

}
